package master;

import java.util.ArrayList;
import java.util.List;

/**
 * 插入区间
 *
 * @author chenyw
 * @date 2022/7/28 10:42
 */
public class M57insert {
    public static void main(String[] args) {
        new M57insert().insert(new int[][]{{1, 5}}, new int[]{6, 8});
    }

    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        boolean isInsert = false;
        List<int[]> list = new ArrayList<int[]>();
        ;
        for (int[] interval : intervals) {
            //在插入区间的右侧且无交集, 此时newInterval需要先被插入
            if (interval[0] > right) {
                if (!isInsert) {
                    isInsert = true;
                    list.add(new int[]{left, right});
                }
                list.add(interval);
            }
            //在插入区间的左侧且无交集
            else if (interval[1] < left) {
                list.add(interval);
            } else {
                //处理并集,并且更新left和right的值
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        if (!isInsert) {
            list.add(new int[]{left, right});
        }
        return list.toArray(new int[list.size()][2]);
    }
}


    //太繁琐，没考虑到元区间无重叠这个条件
//    public int[][] insert(int[][] intervals, int[] newInterval) {
//        if (intervals == null || intervals.length == 0) {
//            return new int[][]{{newInterval[0], newInterval[1]}};
//        }
//        List<int[]> res = new ArrayList<int[]>();
//        int[] arr = new int[2];
//        if (intervals[0][0] < newInterval[0]) {
//            arr[0] = intervals[0][0];
//            arr[1] = intervals[0][1];
////            System.out.println(arr[0]);
//        } else {
//            arr[0] = newInterval[0];
//            arr[1] = newInterval[1];
//        }
//        int pre = arr[1];
//        int i = 0;
//        int a = -1;
//        while (i < intervals.length) {
//            int[] tmp = intervals[i];
//            //单独处理新数组
//            if (newInterval[0] < tmp[0]) {
//                //合并
//                if (newInterval[0] <= pre) {
//                    if (newInterval[1] > pre) {
//                        arr[1] = newInterval[1];
//                        pre = newInterval[1];
//                    }
//                } else {
//                    //用两个变量L,R代替也可以
//                    res.add(new int[] { arr[0], arr[1]});
//                    arr[0] = newInterval[0];
//                    arr[1] = newInterval[1];
//                    pre = arr[1];
//                }
//                i--;
//                a = newInterval[0];
//                System.out.println(a);
//                System.out.println("new:" + newInterval[0]);
//                newInterval[0] = Integer.MAX_VALUE;
//
//            } else {
//                //合并原来数组
//                if (tmp[0] <= pre) {
//                    if (tmp[1] > pre) {
//                        arr[1] = tmp[1];
//                        pre = tmp[1];
//                    }
//                } else {
//                    res.add(new int[] {arr[0], arr[1]});
////                    System.out.println(i);
////                    for (int[] re : res) {
////                        System.out.println(re[0]);
////                        System.out.println(re[1]);
////                    }
//                    arr[0] = tmp[0];
//                    arr[1] = tmp[1];
//                    pre = tmp[1];
//                }
//            }
//            i++;
//        }
//        if (a != -1) {
//            newInterval[0] = a;
//        }
//
//        System.out.println(newInterval[0]);
//        System.out.println(pre);
//        //合并或者追加
//        if (newInterval[0] <= pre) {
//            if (newInterval[1] <= pre) {
//                res.add(new int[]{arr[0], arr[1]});
//            } else {
//                res.add(new int[]{arr[0], newInterval[1]});
//            }
//        } else {
//            res.add(new int[]{arr[0], arr[1]});
//            res.add(new int[]{newInterval[0], newInterval[1]});
//        }
//
//        return res.toArray(new int[res.size()][2]);
//    }
//}
